import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * 注意：答案中不可以包含重复的三元组?
 * 看了答案做的
 */
public class _15三数之和 {
    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result=new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if(i>0 &&nums[i]==nums[i-1]){
                continue;
            }
            int target = -nums[i];
            int left =i+1;
            int right =nums.length-1;
            while(left<right){
                int sum = nums[left]+nums[right];
                if(sum==target){
                    result.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    left++;
                    right--;
                    while(left<right &&nums[left-1]==nums[left]){
                        left++;
                    }
                    while (left<right&&nums[right+1]==nums[right]) {
                        right--;
                    }
                }else if (sum<target){
                    left++;
                }else if (sum>target){
                    right--;
                }
            }

        }
        return result;
    }
    
   

    public static void main(String[] args) {
        System.out.println("=====");
        int[] a ={-1,0,1,2,-1,-4};
        // int[] a ={2,-3,0,-2,-5,-5,-4,1,2,-2,2,0,2,-4,5,5,-10};
        List<List<Integer>> threeSum = threeSum(a);
        for (List<Integer> list : threeSum) {
            for (Integer i : list) {
                System.out.print(i+",");
            }
            System.out.println();
        }
    }

}